//
// Created by 86138 on 2025/6/24.
//

#include "ExchangeSort.h"

namespace sweetcookie10_2 {

    void QSort(SqList &L) {
        QSort(L, 1, L.length);
    }

    void QSort(SqList &L, int low, int high) {
        if (low < high) {
            int pivotloc = Partition(L, low, high);
            QSort(L, low, pivotloc - 1);
            QSort(L, pivotloc + 1, high);
        }
    }

    int Partition(SqList &L, int low, int high) {
        L.base[0] = L.base[low];
        KeyType pivotkey = L.base[0].key;

        while (low < high) {
            while (low < high && L.base[high].key>= pivotkey) {
                high--;
            }
            L.base[low] = L.base[high];

            while (low < high && L.base[low].key <= pivotkey) {
                low++;
            }
            L.base[high] = L.base[low];
        }
        L.base[low] = L.base[0];
        return low;
    }

    void Print(SqList L)
    { int i;
        for(i=1; i<=L.length; i++)
            printf("(%d, %d)", L.base[i].key, L.base[i].otherinfo);
        printf("\n");
    }

    void InputFromFile(FILE* f, RedType &c)
    { fscanf(f, "%d%d", &c.key, &c.otherinfo);
    }
}

//using namespace sweetcookie10_2;
//
//int main() {
//    system("chcp 65001");
//    FILE *f;
//    SqList m;
//    int i;
//    f=fopen("D:\\playground5\\qingdao-university\\10-sort\\f9-1.txt", "r");
//    fscanf(f, "%d", &m.length);
//    for(i=1; i<=m.length; i++)
//        InputFromFile(f, m.base[i]);
//    fclose(f);
//    printf("排序前：\n");
//    Print(m);
//    QSort(m);
//    printf("排序后：\n");
//    Print(m);
//
//    return 0;
//}